#include <vector>
#include<algorithm>
class Solution {
public:
    int ans=0;
    std::vector<int> path;
    int edge = 0;
    
    int totalNQueens(int n) {
        edge = n;
        find(0);
        return ans;
    }
    void find(int n)
    {
        if (n==edge)
        {
            ans++;
            return;
        }
        for (int i=0;i<edge;i++)
        {
           if ( ishave(n,i))
           {
               path.push_back(i);
               find(n+1);
               path.pop_back();
           }
        }
        return ;
    }
    bool ishave(int x, int y)
    {
        
        if (x==0) return true;
        for (int i=0;i<x;i++)
        {
            if (std::abs(x-i)==std::abs(y-path[i]))
            {
                return false;
            }
            if (y==path[i]) return false;
        }
       return true;
    }
};
